Everything about Parallel Programming totally explained
Parallel computing is a form of
computation in which many
instructions are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved
concurrently ("in parallel"). There are several different forms of parallel computing:
bit-level parallelism,
instruction-level parallelism,
data parallelism, and
task parallelism. It has been used for many years, mainly in
high-performance computing, but interest in it has grown in recent years due to the physical constraints preventing
frequency scaling. Parallel computing has become the dominant paradigm in
computer architecture, mainly in the form of
multicore processors. However, in recent years,
power consumption by parallel computers has become a concern.
Parallel computers can be roughly classified according to the level at which the hardware supports parallelism—with
multi-core and
multi-processor computers having multiple processing elements within a single machine, while
clusters,
MPPs, and
grids use multiple computers to work on the same task.
Parallel computer programs are more difficult to write than sequential ones, because concurrency introduces several new classes of potential
software bugs, of which
race conditions are the most common.
Communication and
synchronization between the different subtasks is typically one of the greatest barriers to getting good parallel program performance. The
speedup of a program as a result of parallelization is given by
Amdahl's law.
Background
Traditionally, computer software has been written for serial computation. To solve a problem, an
algorithm is constructed that produces a serial stream of instructions. These instructions are executed on a
central processing unit on one computer. Only one instruction may execute at a time—after that instruction is finished, the next is executed.
Parallel computing, on the other hand, uses multiple processing elements simultaneously to solve a problem. This is accomplished by breaking the problem into independent parts so that each processing element can execute its part of the algorithm simultaneously. The processing elements can be diverse and include resources such as a single computer with multiple processors, several networked computers, specialized hardware, or any combination of the above.
However,
power consumption by a chip is given by the equation P = C × V
2 × F, where P is power, C is the
capacitance being switched per clock cycle (proportional to the number of transistors whose inputs change), V is
voltage, and F is the processor frequency (cycles per second). Increases in frequency increase the amount of power used in a processor. Increasing processor power consumption led ultimately to
Intel's May 2004 cancellation of its
Tejas and Jayhawk processors, which is generally cited as the end of frequency scaling as the dominant computer architecture paradigm.
Moore's Law is the empirical observation that transistor density in a microprocessor doubles every 18 to 24 months. Despite power consumption issues, and repeated predictions of its end, Moore's law is still in effect. With the end of frequency scaling, these additional transistors (which are no longer used for frequency scaling) can be used to add extra hardware for parallel computing.
Amdahl's law and Gustafson's law
Theoretically, the speed-up from parallelization should be linear—doubling the number of processing elements should halve the runtime, and doubling it a second time should again halve the runtime. However, very few parallel algorithms achieve optimal speed-up. Most of them have a near-linear speed-up for small numbers of processing elements, which flattens out into a constant value for large numbers of processing elements.
The potential speedup of an algorithm on a parallel computing platform is given by
Amdahl's law, originally formulated by
Gene Amdahl in the 1960s. It states that a small portion of the program which can't be parallelized will limit the overall speed-up available from parallelization. Any large mathematical or engineering problem will typically consist of several parallelizable parts and several non-parallelizable (sequential) parts. This relationship is given by the equation:
»
where S is the speed-up of the program (as a factor of its original sequential runtime), and P is the fraction that's parallelizable. If the sequential portion of a program is 10% of the runtime, we can get no more than a 10x speedup, regardless of how many processors are added. This puts an upper limit on the usefulness of adding more parallel execution units. "When a task can't be partitioned because of sequential constraints, the application of more effort has no effect on the schedule. The bearing of a child takes nine months, no matter how many women are assigned."
Gustafson's law is another law in computer engineering, closely related to Amdahl's law. It can be formulated as:
»
where P is the number of processors, S is the speed-up, and
the non-parallelizable part of the process. Amdahl's law assumes a fixed-problem size and that the size of the sequential section is independent of the number of processors, whereas Gustafson's law doesn't make these assumptions.
Dependencies
Understanding
data dependencies is fundamental in implementing
parallel algorithms. No program can run more quickly than the longest chain of dependent calculations (known as the
critical path), since calculations that depend upon prior calculations in the chain must be executed in order. However, most algorithms don't consist of just a long chain of dependent calculations; there are usually opportunities to execute independent calculations in parallel.
Let P
i and P
j be two program fragments. Bernstein's conditions describe when the two are independent and can be executed in parallel. Let I
i be all of the input variables to P
i and O
i the output variables, and likewise for P
j. P
i and P
j are independent if they satisfy
-
-
-
Violation of the first condition introduces a flow dependency, corresponding to first statement's producing a result used by the second statement. The second condition represents an
anti-dependency, when the first statement overwrites a variable needed by the second expression. The third and final condition, q, is an output dependency. When two variables write to the same location, the final output must have arisen from the second statement.
Consider the following functions, which demonstrate several kinds of dependencies:
1:
function Dep(a, b)
2: c := a·b
3: d := 2·c
4:
end function
Operation 3 in
Dep(a, b) can't be executed before (or even in parallel with) operation 2, because operation 3 uses a result from operation 2. It violates condition 1, and thus introduces a flow dependency.
1:
function NoDep(a, b)
2: c := a·b
3: d := 2·b
4: e := a+b
5:
end function
In this example, there are no dependencies between the instructions, so they can all be run in parallel.
Bernstein’s conditions don't allow memory to be shared between different processes. For that, some means of enforcing an ordering between accesses is necessary, such as
semaphores,
barriers or some other
synchronization method.
Race conditions, mutual exclusion, synchronization, and parallel slowdown
Subtasks in a parallel program are often called
threads. Some parallel computer architectures use smaller, lightweight versions of threads known as
fibers, while others use bigger versions known as
processes. However, "threads" is generally accepted as a generic term for subtasks. Threads will often need to update some
variable that's shared between them. The instructions between the two programs may be
interleaved in any order. For example, consider the following program:
| Thread A |
Thread B |
| 1A: Read variable V |
1B: Read variable V |
| 2A: Add 1 to variable V |
2B: Add 1 to variable V |
| 3A Write back to variable V |
3B: Write back to variable V |
If instruction 1B is executed between 1A and 3A, or if instruction 1A is executed between 1B and 3B, the program will produce incorrect data. This is known as a
race condition. The programmer must use a
lock to provide
mutual exclusion. A lock is a programming language construct that allows one thread to take control of a variable and prevent other threads from reading or writing it, until that variable is unlocked. The thread holding the lock is free to execute its
critical section (the section of a program that requires exclusive access to some variable), and to unlock the data when it's finished. Therefore, to guarantee correct program execution, the above program can be rewritten to use locks:
| Thread A |
Thread B |
| 1A: Lock variable V |
1B: Lock variable V |
| 2A: Read variable V |
2B: Read variable V |
| 3A: Add 1 to variable V |
3B: Add 1 to variable V |
| 4A Write back to variable V |
4B: Write back to variable V |
| 5A: Unlock variable V |
5B: Unlock variable V |
One thread will successfully lock variable V, while the other thread will be
locked out—unable to proceed until V is unlocked again. This guarantees correct execution of the program. Locks, while necessary to ensure correct program execution, can greatly slow a program.
Locking multiple variables using
non-atomic locks introduces the possibility of program
deadlock. An atomic lock locks multiple variables all at once. If it can't lock all of them, it doesn't lock any of them. If two threads each need to lock the same two variables using non-atomic locks, it's possible that one thread will lock one of them and the second thread will lock the second variable. In such a case, neither thread can complete, and deadlock results.
Many parallel programs require that their subtasks
act in synchrony. This requires the use of a
barrier. Barriers are typically implemented using a software lock. One class of algorithms, known as
lock-free and wait-free algorithms, altogether avoids the use of locks and barriers. However, this approach is generally difficult to implement and requires correctly designed data structures.
Not all parallelization results in speed-up. Generally, as a task is split up into more and more threads, those threads spend an ever-increasing portion of their time communicating with each other. Eventually, the overhead from communication dominates the time spent solving the problem, and further parallelization (that is, splitting the workload over even more threads) increases rather than decreases the amount of time required to finish. This is known as
parallel slowdown.
Fine-grained, coarse-grained, and embarrassing parallelism
Applications are often classified according to how often their subtasks need to synchronize or communicate with each other. An application exhibits fine-grained parallelism if its subtasks must communicate many times per second; it exhibits coarse-grained parallelism if they don't communicate many times per second, and it's
embarrassingly parallel if they rarely or never have to communicate. Embarrassingly parallel applications are considered the easiest to parallelize.
Consistency models
Parallel programming languages and parallel computers must have a
consistency model (also known as a memory model). The consistency model defines rules for how operations on
computer memory occur and how results are produced.
One of the first consistency models was
Leslie Lamport's
sequential consistency model. Sequential consistency is the property of a parallel program that its parallel execution produces the same results as a sequential program. Specifically, a program is sequentially consistent if "... the results of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program".
Software transactional memory is a common type of consistency model. Software transactional memory borrows from
database theory the concept of
atomic transactions and applies them to memory accesses.
Mathematically, these models can be represented in several ways.
Petri nets, which were introduced in Carl Adam Petri's 1962 doctoral thesis, were an early attempt to codify the rules of consistency models. Dataflow theory later built upon these, and
Dataflow architectures were created to physically implement the ideas of dataflow theory. Beginning in the late 1970s,
process calculi such as
calculus of communicating systems and
communicating sequential processes were developed to permit algebraic reasoning about systems composed of interacting components. More recent additions to the process calculus family, such as the
π-calculus, have added the capability for reasoning about dynamic topologies. Logics such as Lamport's
TLA+, and mathematical models such as
traces and
Actor event diagrams, have also been developed to describe the behavior of concurrent systems.
Flynn's taxonomy
Michael J. Flynn created one of the earliest classification systems for parallel (and sequential) computers and programs, now known as
Flynn's taxonomy. Flynn classified programs and computers by whether they were operating using a single set or multiple sets of instructions, whether or not those instructions were using a single or multiple sets of data.
The single-instruction-single-data (SISD) classification is equivalent to an entirely sequential program. The single-instruction-multiple-data (SIMD) classification is analogous to doing the same operation repeatedly over a large data set. This is commonly done in
signal processing applications. Multiple-instruction-single-data (MISD) is a rarely used classification. While computer architectures to deal with this were devised (such as
systolic arrays), few applications that fit this class materialized. Multiple-instruction-multiple-data (MIMD) programs are by far the most common type of parallel programs.
According to
David A. Patterson and
John L. Hennessy, "Some machines are hybrids of these categories, of course, but this classic model has survived because it's simple, easy to understand, and gives a good first approximation. It is also—perhaps because of its understandability—the most widely used scheme."
Types of parallelism
Bit-level parallelism
From the advent of
very-large-scale integration (VLSI) computer-chip fabrication technology in the 1970s until about 1986, speed-up in computer architecture was driven by doubling
computer word size—the amount of information the processor can execute per cycle. Increasing the word size reduces the number of instructions the processor must execute to perform an operation on variables whose sizes are greater than the length of the word. For example, where an
8-bit processor must add two
16-bit integers, the processor must first add the 8 lower-order bits from each integer using the standard addition instruction, then add the 8 higher-order bits using an add-with-carry instruction and the
carry bit from the lower order addition; thus, an 8-bit processor requires two instructions to complete a single operation, where a 16-bit processor would be able to complete the operation with a single instruction.
Historically,
4-bit microprocessors were replaced with 8-bit, then 16-bit, then 32-bit microprocessors. This trend generally came to an end with the introduction of 32-bit processors, which has been a standard in general-purpose computing for two decades. Not until recently (circa 2003-2004), with the advent of
x86-64 architectures, have
64-bit processors become commonplace.
Instruction-level parallelism
A computer program is, in essence, a stream of instructions executed by a processor. These instructions can be
re-ordered and combined into groups which are then executed in parallel without changing the result of the program. This is known as instruction-level parallelism. Advances in instruction-level parallelism dominated computer architecture from the mid-1980s until the mid-1990s.
Modern processors have multi-stage
instruction pipelines. Each stage in the pipeline corresponds to a different action the processor performs on that instruction in that stage; in other words, a processor with N pipeline stages can have up to N different instructions at different stages of completion. The canonical example of a pipelined processor is a RISC processor, with five stages: instruction fetch, decode, execute, memory access, and write back. The
Pentium 4 processor had a 35-stage pipeline.
In addition to instruction-level parallelism from pipelining, some processors can issue more than one instruction at a time. These are known as
superscalar processors. Instructions can be grouped together only if there's no
data dependency between them.
Scoreboarding and the
Tomasulo algorithm (which is similar to scoreboarding but makes use of
register renaming) are two of the most common techniques for implementing out-of-order execution and instruction-level parallelism.
Data parallelism
Data parallelism is parallelism inherent in
program loops, which focuses on distributing the data across different computing nodes to be processed in parallel. "Parallelizing loops often leads to similar (not necessarily identical) operation sequences or functions being performed on elements of a large data structure." Many scientific and engineering applications exhibit data parallelism.
A loop-carried dependency is the dependence of a loop iteration on the output of one or more previous iterations. Loop-carried dependencies prevent the parallelization of loops. For example, consider the following
pseudocode that computes the first few
Fibonacci numbers:
1: prev2 := 0
2: prev1 := 1
3: cur := 1
4: do:
5: CUR := PREV1 + PREV2
6: PREV2 := PREV1
7: PREV1 := CUR
8: while (CUR < 10)
This loop can't be parallelized because CUR depends on itself (PREV1) and PREV2, which are computed in each loop iteration. Since each iteration depends on the result of the previous one, they can't be performed in parallel. As the size of a problem gets bigger, the amount of data-parallelism available usually does as well.
Task parallelism
Task parallelism is the characteristic of a parallel program that "entirely different calculations can be performed on either the same or different sets of data". Distributed memory refers to the fact that the memory is logically distributed, but often implies that it's physically distributed as well.
Distributed shared memory is a combination of the two approaches, where the processing element has its own local memory and access to the memory on non-local processors. Accesses to local memory are typically faster than accesses to non-local memory.
Computer architectures in which all of main memory can be accessed with equal
latency and
bandwidth are known as
Uniform Memory Access (UMA) systems. Typically, only a
shared memory system (where the memory isn't physically distributed) can achieve these. A system that doesn't have this property is known as a
Non-Uniform Memory Access (NUMA) architecture. Distributed memory systems have non-uniform memory access.
Computer systems make use of
caches—small, fast memories located close to the processor which store temporary copies of memory values (nearby in both the physical and logical sense). Parallel computer systems have difficulties with caches that may store the same value in more than one location, with the possibility of incorrect program execution. These computers require a
cache coherency system, which keeps track of cached values and strategically purges them, thus ensuring correct program execution.
Bus snooping is one of the most common methods for keeping track of which values are being accessed (and thus should be purged). Designing large, high-performance cache coherence systems is a very difficult problem in computer architecture. As a result, shared-memory computer architectures don't scale as well as distributed memory systems do.
Bus contention prevents bus architectures from scaling. As a result, SMPs generally don't comprise more than 32 processors. "Because of the small size of the processors and the significant reduction in the requirements for bus bandwidth achieved by large caches, such symmetric multiprocessors are extremely cost-effective, provided that a sufficient amount of memory bandwidth exists." Clusters are composed of multiple standalone machines connected by a network. While machines in a cluster don't have to be symmetric,
load balancing is more difficult if they're not. The most common type of cluster is the
Beowulf cluster, which is a cluster implemented on multiple identical
commercial off-the-shelf computers connected with a
TCP/IP Ethernet local area network. Beowulf technology was originally developed by
Thomas Sterling and
Donald Becker. The vast majority of the
TOP500 supercomputers are clusters.
Massive parallel processing
A massively parallel processor (MPP) is a single computer with many networked processors. MPPs have many of the same characteristics as clusters, but they're usually larger, typically having "far more" than 100 processors. In an MPP, "each CPU contains its own memory and copy of the operating system and application. Each subsystem communicates with the others via a high-speed interconnect."
Blue Gene/L, the fastest supercomputer in the world according to the TOP500 ranking, is an MPP.
Grid computing
Grid computing is the most distributed form of parallel computing. It makes use of computers communicating over the
Internet to work on a given problem. Because of the low bandwidth and extremely high latency available on the Internet, grid computing typically deals only with embarrassingly parallel problems.
Many grid computing applications have been created, of which
SETI@home and
Folding@Home are best-known examples.
Most grid computing applications use
middleware—software that operates between the operating system and the application, which manages network resources and standardizes the software interface for grid computing applications. The most common grid computing middleware is the
Berkeley Open Infrastructure for Network Computing (BOINC). Often, grid computing software makes use of "spare cycles", performing computations at times when a computer is idling.
Specialized parallel computers
Within parallel computing, there are specialized parallel devices that remain niche areas of interest. While not
domain-specific, they tend to be applicable to only a few classes of parallel problems.
Reconfigurable computing with field-programmable gate arrays
Reconfigurable computing is the use of a field-programmable gate array (FPGA) as a co-processor to a general-purpose computer. An FPGA is, in essence, a computer chip that can rewire itself for a given task.
FPGAs can be programmed with hardware description languages such as VHDL or Verilog. However, programming in these languages can be tedious. Several vendors have created C to HDL languages that attempt to emulate the syntax and/or semantics of the C programming language, with which most programmers are familiar. The best known C to HDL languages are Mitrion-C, Impulse C, DIME-C, and Handel-C.
AMD's decision to open its HyperTransport technology to third-party vendors has become the enabling technology for high-performance reconfigurable computing. According to Michael R. D'Amour, CEO of DRC Computer Corporation, "when we first walked into AMD, they called us 'the socket stealers.' Now they call us their partners." Computer graphics processing is a field dominated by data parallel operations—particularly linear algebra matrix operations.
In the early days, GPGPU programs used the normal graphics APIs for executing programs. However, recently several new programming languages and platforms have been built to do general purpose computation on GPUs with both Nvidia and AMD releasing programming environments with CUDA and CTM respectively. Other GPU programming languages are BrookGPU, PeakStream, and RapidMind. Nvidia has also released specific products for computation in their Tesla series.
Application-specific integrated circuits
Several Application-specific integrated circuit (ASIC) approaches have been devised for dealing with parallel applications.
Because an ASIC is (by definition) specific to a given application, it can be fully optimized for that application. As a result, for a given application, an ASIC tends to outperform a general-purpose computer. However, ASICs are created by X-ray lithography. This process requires a mask, which can be extremely expensive. A single mask can cost over a million US dollars. (The smaller the transistors required for the chip, the more expensive the mask will be.) Meanwhile, performance increases in general-purpose computing over time (as described by Moore's Law) tend to wipe out these gains in only one or two chip generations. They are closely related to Flynn's SIMD classification.
Mainstream parallel programming languages remain either explicitly parallel or (at best) partially implicit, in which a programmer gives the compiler directives for parallelization. A few fully implicit parallel programming languages exist—SISAL, Parallel Haskell, and (for FPGAs) Mitrion-C—but these are niche languages that are not widely used.
Application checkpointing
The larger and more complex a computer, the more that can go wrong and the shorter the
mean time between failures.
Application checkpointing is a technique whereby the computer system takes a "snapshot" of the application—a record of all current resource allocations and variable states, akin to a
core dump; this information can be used to restore the program if the computer should fail. Application checkpointing means that the program has to restart from only its last checkpoint rather than the beginning. For an application that may run for months, that's critical. Application checkpointing may be used to facilitate
process migration.
Applications
As parallel computers become larger and faster, it becomes feasible to solve problems that previously took too long to run. Parallel computing is used in a wide range of fields, from
bioinformatics (to do
protein folding) to economics (to do simulation in
mathematical finance). Common types of problems found in parallel computing applications are:
Dense linear algebra
Sparse linear algebra
Spectral methods (such as Cooley-Tukey Fast Fourier transform)
N-body problems (such as Barnes-Hut simulation)
Structured grid problems (such as Lattice Boltzmann methods),
Unstructured grid problems (such as found in finite element analysis)
Monte Carlo simulation
Combinational logic (such as brute-force cryptographic techniques)
Graph traversal (such as Sorting algorithms)
Dynamic programming
Branch and bound methods
Graphical models (such as detecting Hidden Markov models and constructing Bayesian networks)
Finite State Machine simulation
History
The origins of true (MIMD) parallelism go back to Federico Luigi, Conte Menabrea and his "Sketch of the Analytic Engine Invented by Charles Babbage." IBM introduced the 704 in 1954, through a project in which Gene Amdahl was one of the principal architects. It became the first commercially available computer to use fully automatic floating point arithmetic commands. In 1958, IBM researchers John Cocke and Daniel Slotnick discussed the use of parallelism in numerical calculations for the first time. Burroughs Corporation introduced the D825 in 1962, a four-processor computer that accessed up to 16 memory modules through a crossbar switch. In 1967, Amdahl and Slotnick published a debate about the feasibility of parallel processing at American Federation of Information Processing Societies Conference. In 1964, Slotnick had proposed building a massively parallel computer for the Lawrence Livermore National Laboratory. When it was finally ready to run its first real application in 1976, it was outperformed by existing commercial supercomputers such as the Cray-1.
Further Information
Get more info on 'Parallel Programming'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://parallel_computing.totallyexplained.com">Parallel computing Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
